package Exercise;

/**
 * @author dx
 * @version 1.0
 * @date 2022/6/11 14:27
 * @description:  快排是一种分治思想的排序算法，主要分为以下三个步骤：
 * 1、定基准，首先随机选择一个元素作为基准(一般选取第一个或者最后一个)
 * 2、划分区，所有比基准小的元素置于基准左侧，比基准大的元素置于基准右侧
 * 3、递归调用，递归地调用此划分过程
 * https://pdai.tech/md/algorithm/alg-sort-x-fast.html
 *
 *
 * 快排的最好情况和最坏情况：
 *快速排序的时间性能取决于快速排序递归的深度，
 * 最好：分区每次都很均与，如果排序n个关键字，则递归树的深度就是long2n+1,即需要递归log2n次，在最优的情况
 * 时间复杂度是O(nlongn)
 * 最坏:待排序的序列是逆序的，每次划分只得到比上一次划分少一个记录的子序列，最终时间复杂度为O(n^2)
 */
public class qsort1 {
    public static void main(String[] args) {
        int []test = {1,4,2,9,4,37,12,6};
        quickSort(test,0,test.length-1);
        for(int x:test){
            System.out.println(x);
        }
    }

    public static void quickSort(int []a,int left,int right){
        if(left > right){
            return;
        }
        int i = left;
        int j = right;
        int x = a[i];
        while(i < j){
            while (i<j && a[j]>x){
                j--;
            }
            if(i < j){
                a[i++] = a[j];
            }
            while (i < j && a[i]<x){
                i++;
            }
            if(i < j){
                a[j--] = a[i];
            }
        }
        a[i] = x;
        quickSort(a,left,i-1);
        quickSort(a,i+1,right);
    }
}
